CF 1632C

别傻看着题干了，列一列代价的式子。

有必要进行多次操作二吗？仔细想一想，并给出是或不是的详细证明。

对任意 $a$ 与 $b$，$a,b\le a\mathrm{OR}b$.

事实是，我们最多只需要进行一次操作二，进行多次操作二一定是不优的。简单证明如下：显然我们不需要一口气进行两次操作二。那么假设我们在两次操作二之间插入一次操作一，则后面的这次操作二无论如何都是没有必要的。

搞清楚这点之后我们的思路就清晰很多了。分两种情况讨论：

不进行操作一。代价显然为 $(b-a)$。

进行操作一。何时进行？我们需要详细分析这些操作的代价，由于一旦执行操作后 $b\le a$，此时我们只能进行操作一。显然设我们已经执行了若干次操作一并得到了 $a^{\prime }$ 与 $b^{\prime }$，上述过程的代价则为 $(a^{\prime }-a)+(b^{\prime }-b)+(b^{\prime }\mathrm{OR}{a}^{\prime })-b^{\prime }+1$，整理得到 $(a^{\prime }+b^{\prime }\mathrm{OR}{a}^{\prime })-(a+b-1)$。式子后半部分的 $(a+b-1)$ 为定值，无需处理。我们希望最小化前面的部分。由于这个式子找不到什么规律，于是直接暴力枚举所有的 $a^{\prime }\in [a,b]$，考虑此时如何构造一个 $b^{\prime }$ 使 $(b^{\prime }\mathrm{OR}{a}^{\prime })$ 最小，逐位考虑：

• 若 $a^{\prime }$ 与 $b$ 当位均为 $0$ 或 $1$，保持原状即可。
• 若 $a^{\prime }$ 当位为 $1$，$b$ 当位为 $0$，同样保持原状即可。
• 若 $a^{\prime }$ 当位为 $0$，$b$ 当位为 $1$，若存在 $a^{\prime }$ 为 $1$ 且 $b$ 对应位为 $0$ 的更高位，则可以通过加一定值“移走” $b$ 的这个 $1$ 使得取或后该位结果为 $0$；但若不存在这样的位，保持原状即可。

时间复杂度为 $\mathrm{\Theta }(b-a)$。